\chapter{Analyse des performances pour les systèmes multicoeurs}
%%%% partie 1 

\section{les métriques de performance multicoeur}
L'efficacité est en grande partie indépendante du nombre de nœuds et extrêmement dépendante du nombre de cœurs par nœud.

\subsection{Les Métriques qui caractérisent la performance}
\begin{itemize}
  \item \textit{Flops Per Cycle} (FPC) : Nombre d'opérations flottantes par cycle.
  \item \textit{Instructions Per Cycle} (IPC) : nombre d'instructions par cycle (CPU).
  \item \textit{Loads Per Cycle} (LPC) : nombre de \textit{loads} par cycle (MEMOIRE).
\end{itemize}
Si l'un de ces métriques s'approche de la borne maximale, nous pouvons en conclure que les performances sont bonnes et que la seule amélioration encore possible est l'optimisation algorithmique.\\
Si les trois métriques sont en dessous de la performance crête cela signifie que le goulot d'étranglement se situe au niveau de la mémoire.\\
La figure \ref{princ_func} présente les métriques pour les principales fonctions dans HOMME.\\

%%% fig1
\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=10cm]{images/HOMME_perf.png}
		\caption{Performance des métriques pour les fonctions HOMME}
		\label{princ_func}
	\end{center}
\end{figure}

Il y a 3 fonctions qui atteignent des niveaux de performance très importante, elles sont des fonctions \textit{CPU-bound} (le temps d'exécution d'une instruction est déterminé principalement par la vitesse du processeur central), les autres  fonctions sont \textit{memory-bound} (l'exécution dépend de la taille de la mémoire et dela vitesse d'accès mémoire).\\

\subsection{Les limites des métriques de performance monocoeur}
Les métriques utilisées dans les systèmes monocoeur ne sont pas fiables pour le calcul de performance des systèmes multicores.
\begin{itemize}
  \item Non fiabilité du taux de \textit{miss} L1 : à cause du système de comptabilisation des \textit{miss}.
   Les premier accès à une ligne qui n'est pas encore chargée en L1 est comptabilisés comme des cache\textit{miss}. Ce premier cache miss déclenche l'action du prefetcher qui consiste en le chargement de la ligne de cache. Les accès suivants à des données de la même ligne de cache ne sont pas considérés comme des cache miss, alors que le prefetcher n'a peut-être pas fini le chargement.
  \item Non fiabilité du taux de \textit{miss} L2  : les auteurs de l'article ont supposé que si le taux de \textit{miss} en L2 n'est pas élevé forcément le système ne souffre pas au niveau de L3 et DRAM, mais avec les expériences de la mesure des taux de \textit{miss} pour les fonctions de HOMME, il ont  montré le contraire un taux de \textit{miss} très important en L3 et DRAM par rapport à L2 très petit.
\end{itemize}

%%% fig2
\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=10cm]{images/Miss_HOMME.png}
		\caption{les taux de miss en L1,L2,L3 et DRAM pour les fonctions HOMME}
	\end{center}
	\label{miss_homme}
\end{figure}


La figure \ref{miss_homme} montre les taux de \textit{miss} L1, L2, L3, et DRAM.
Plus on descend en profondeur de l'architecture mémoire, plus e taux de miss augmente. L'optimisation classique de CPU peux être non productive. Certaines optimisations réduisent les performances à la place de les améliorer.

La figure \ref{flag} illustre les performances obtenues sur système multicoeur avec les optimisations habituelles invoquant les flags du compilateur. Elle permet de comparer les résultats obtenus sur un processeur monocoeur et un processeur \textit{quadcores}.

%%% fig3
\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=7cm]{images/compil.png}
		\caption{Les effets des flags de compilation sur les performance pour les multicoeur et le monocoeur.}
		\label{flag}
	\end{center}
\end{figure}

Avec le \textit{flag} -O3 la performance a presque doublé pour le monocoeur mais pas pour le \textit{quadcore}. L'ajout de l'optimisation préséntée dans la prochaine section (microfission de boucles) fait baisser les performances du monocoeur mais augmente celles du multicoeur.

%%%% partie 2 

\section{Goulots d'étranglement spécifiques aux systèmes multicoeurs}
%%% fig4
\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=10cm]{images/multi.png}
		\caption{les principaux bottlenecks des multicoeurs.}
	\end{center}
\end{figure}
En général, les problèmes dans le système de mémoire s'écoulent vers le bas : le problème de capacité en cache L3 augmente la demande de bande passante en \textit{off-chip}, qui a son tour rend plus intense les DRAM \textit{page misses}.\\

\subsection{Capacité du cache L3}
Pour les mesures au niveau du cache L3, les auteurs de notre article se sont basés sur les \textit{natives hardware counters} relatifs au processeur.\\
En cas d’augmentation du taux de \textit{miss} en L3 avec l'augmentation de la densité du noyau, il est probable que le problème soit dû à la capacité du cache L3. Ce type de problème induit très souvent un problème de bande passante \textit{off-chip}. 
La solution proposée est la suivante :
\begin{itemize}
  \item Réduire l'empreinte mémoire dans le cache avec la sérialisation des données.
  \item Stocker des données intermédiaires pour réduire le calcul.
  \item Fonctionner sur plusieurs valeurs à la fois, au lieu d'une à la fois (microfission).
\end{itemize}

\subsection{Off-chip bandwith}
La bande passante \textit{off-chip} est reconnue pour être le principal goulot d'étranglement des applications multicoeurs.
Pour déterminer les performances  en bande passante \textit{off-chip}, il est recommandé d'étudier les fonctions une à une car la moyenne peut induire en erreur (pour éviter les fonctions qui n'ont pas d'accès à la bande passante \textit{off-chip}).\\ 
La mesure de l'étranglement de la bande passante en \textit{off-chip} ne peut être calculée convenablement que si la fonction est lancée sur un monocoeur sinon on aura l'impression que l'utilisation en bande est très petite et la performance médiocre.
La mesure de la performance peux être effectuée par le total de la bande passante \textit{off-chip} divisé par le nombre de cœurs par \textit{chip}.\\

\subsection{DRAM pages}
Une page DRAM est une ligne de donnée qui a été lue depuis la banque mémoire et stockée en cache dans la DRAM.
Les \textit{DRAM page miss} constituent une problématique majeure pour les sytèmes multicoeurs. 
En effet, les \textit{DRAM page miss} ont des conséquences majeures : 
\begin{itemize}
  \item La contention des pages DRAM impacte la performance :
L’accès à une page déjà ouverte induit la fermeture de la page précédente et l'ouverture d'une nouvelle page, ce qui augmente le temps d'exécution et le taux de \textit{miss} au niveau de la DRAM. Pour ça les contrôleurs DRAM des architectures multicoeurs utilisent les planificateurs et les mémoires tampons, mais le problème persiste toujours avec les limites de la mémoire tampon.\\
  \item L'optimisation des DRAM n'est pas nécessairement complexe : il suffit de déployer des transformation de haut niveau sur le code pour éviter les conflits de cache et augmenter la performance .
\end{itemize}

\section{Difficultés de la prise mesure}
\noindent Les architectures multicoeurs ont tendance à produire des interactions complexe de hiérarchie mémoire, les difficulté issues de ce phénomène sont :
\begin{itemize}
  \item L'hyper sensibilité des effets mémoire : elles dépendent de l'état de tous les caches et les bancs de DRAM dans le système. 
  \item La contention de la mémoire a tendance à apparaître en rafale, il faut observer à la bonne échelle pour les voir.
  \item Les interactions mémoire ont tendance à être indéterministes. (dépendent des interactions des threads)
  \item Les goulots d'étranglement mémoire  peuvent être fortement non-locaux et souvent causé par les appels aux fonctions précédentes.
  \item Les perturbations au niveau de la mémoire dues à la mesure.
\end{itemize}
Il est très difficile d'isoler et de retirer les pertubations créées par la mesure elle-même.

\subsection{Effet de Core Skew}
Chaque noyau peut-être dans une phase un différente de l'exécution, différentes fonctions peuvent être exécutées sur différents cœurs en même temps. Cet effet peux être causé par les interaction non déterministes, un événement mémoire intense avec un taux faible de sérialisation ou un noyau unique exerçant des fonctions uniques.

La figure \ref{skew} montre à quel point l'exécution d'une même fonction peut changer.

\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=10cm]{images/skew.png}
		\caption{Variation d'exécution de la fonction PreqRobert}
		\label{skew}
	\end{center}
\end{figure}

L'effet est que un événement intense est lancé au cours du temps, et il reste en fonctionnement du moment où le premier noyau a commencé jusqu'à ce que le dernier noyau  termine. Cela qui ralentit les performances.

Afin d'éviter cet effet la solution selon les auteurs est de minimiser le décalage au niveau des pas d'horloge et de faire de façon que les noyaux exécutent les opérations les plus semblables.
Les auteurs ont également développé un système hiérarchique avec lequel ils collectent les données sur des périodes de millisecondes, ces moyennes cumulées sont utilisées pour les statistiques sur les variations temporelles des exécutions.
 
\subsection{Minimiser les perturbations de la prise de mesure}
La problématique évoquée est le fait que les fonctions de mesure peuvent impacter le temps d'exécution des fonctions, et ainsi impacter les performances.

%%% fig5
\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=7cm]{images/exec1.png}
		\caption{les durées d'execution des principales fonctions HOMME}
		\label{temps}
	\end{center}
\end{figure}

La figure \ref{temps} montre les différences en termes de nombre moyen de cycles pour l'exécution des fonctions de HOMME. 
20\% d'entre elles durent moins de 2000 cycles. Ces fonctions qui s'exécutent rapidement, sont d'autant plus impactées et nécessitent une attention toute particulière.

Par exemple : l'utilisation de \textit{PAPI READ} pour consulter la valeur d'un compteur de performance, même si cet appel est négligeable par rapport au code, a un impact sur la performance de la mémoire.

Voici quelques outils recommandés pour leur faible impact :
\begin{itemize}
	\item Costum PAPI
	\item PerCTR
	\item gprof et TAU	
\end{itemize}


Études et classification des outils par les auteurs :
\begin{itemize}
	\item Gprof est l'outil le plus simple a utilier, mais il n'est perfomant que pour les trois plus petites fonctions de HOMME.
	\item HPCToolkit a permi d'isoler 3 des 11 parties les plus importantes du code.
	\item PerfExpert a étécréé pour être plus facile d'utilisation que gProf, et fonctionne raisonnablement bien.
\end{itemize}

Pour des fonctions de l'ordre  de un million de cycles d'exécution les auteurs utilisent l'instrumentation de code.

\subsection{Résumé de l'analyse multicoeur}
Proposition d'une méthode systématique pour l'optimisation des performances pour les systèmes multicœurs
\begin{itemize}
  \item[1.]Utilisation d'un outil comme \textit{gprof} pour identifier les fonctions les plus importantes pour le temps total d'exécution, et lancer ce test avec le maximum et le minimum de noyaux pour déterminer les fonctions les plus faibles en scalabilté \textit{intracore}.
  \item[2.]Comparer les valeurs de l'\textit{IPC, FPC et LPC} pour ces fonctions à une densité maximale dans le noyau pour déterminer la marge d'optimisation, collecte des données (L3 et DRAM \textit{misses}) pour les fonctions avec de mauvaises performances.
  \item[3.]Si les taux L3 \textit{miss} augmentent avec la densité du noyau, se concentrer sur les optimisations qui minimisent l'empreinte mémoire cache ou des variables temporaires, ou sérialiser les accès des données.
  \item[4.]Si il y a des fonctions qui, avec une  densité de noyau  minimum, dépassent largement leur bande passante  \textit{off-chip}, il faut procéder par les échanges de boucles qui peuvent permettre une plus grande réutilisation de données, ou remplacer les données stockées avec du calcul redondant.
  \item[5.]Si il y a \textit{DRAM bank miss} avec une densité minimum il faut penser à la réorganisation des boucles et accéder à un seul tableau a la fois.
  \item[6.]TAU, HPCToolkit ou PAPI : sont suffisants pour les fonctions moyennes et grandes.
TAU run ou PerCtr code : sont dédiées aux fonctions très petites.\\
\end{itemize}
